package com.zklh.leetcode.top100;

import com.zklh.leetcode.tree.model.TreeNode;

/**
 * 从前序与中序遍历构造二叉树
 *
 * @author 坐看落花
 * @version 1.0
 * @date 2021/11/13 9:44
 */
public class Solution105 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }

    private TreeNode buildTree(int[] preorder, int l1, int r1, int[] inorder, int l2, int r2) {
        if (l1 > r1) {
            return null;
        }
        TreeNode treeNode = new TreeNode(preorder[l1]);
        int position = l2;
        for (int i = l2; i <= r2; i++) {
            if (inorder[i] == preorder[l1]) {
                position = i;
                break;
            }
        }
        int lLen = position-l2;

        treeNode.left = buildTree(preorder, l1+1, l1+lLen, inorder, l2, position-1);
        treeNode.right = buildTree(preorder, l1+lLen+1, r1, inorder, position+1, r2);

        return treeNode;
    }

    public static void main(String[] args) {
        Solution105 solution = new Solution105();
        int[] preorder = {3,9,20,15,7};
        int[] inorder = {9,3,15,20,7};
        TreeNode node = solution.buildTree(preorder, inorder);

    }
}
